/* This program calculates the selection of items needed to maximize the value
 * of the knapsack.
 */
#include <stdio.h>

/* We cheat. Infinity is >= 9999 */
#define INFINITY 9999

struct item {
	int weight;
	int value;
};

struct item items[] = {
	{1, 3},
	{2, 1},
	{3, 3},
	{2, 1},
};

int num = 4;

/* used[i][j] tells us if item i was used to achieve weight j */
int used[100][100];
int dp[100][100];

/* Print a (m x n) array */
void print_arr(int arr[][100], int m, int n)
{
	int i,j;

	printf("%4d | ",0);
	for(j=0; j < n; j++)
		printf("%4d ",j);
	printf("\n");

	printf("-------");
	for(j=0; j < n; j++)
		printf("-----");
	printf("\n");

	for (i = 0; i < m; i++) {
		printf("%4d | ", items[i].value);

		for (j=0; j < n; j++) {
			if (arr[i][j] == INFINITY)
				printf("%4c ", '%');
			else
				printf("%4d ", arr[i][j]);
		}
		printf("\n");
	}
	printf("\n");
}

void initialize(int weight, int num)
{
	int i;

	/* To realise a weight of 0, we need 0 items */
	for (i=0; i < num; i++)
		dp[i][0] = 0;

	/* Initialize the first row of dynamic programming array. This row has
	 * the max value attainable with 1 item.
	 */
	for(i = 1; i <= weight; i++) {
		/* If item weighs more than the max weight, value attainable is
		 * 0
		 */
		if (i < items[0].weight)
			dp[0][i] = 0;
		else
			dp[0][i] = items[0].value;

		if(dp[0][i])
			used[0][i] = 1;
		else
			used[0][i] = 0;
	}

}

void knapsack(int weight, int num)
{
	int i,j;

	for (i = 1; i < num; i++) {
		for (j = 1; j <= weight; j++) {
			/* The current item being considered is greater than
			 * the current weight. We can't add it */
			if (items[i].weight > j) {
				dp[i][j] = dp[i - 1][j];
				used[i][j] = 0;
			} else {
				/* Compare adding the item or not adding it.
				   We know that the current weight can be
				   realised by using items from only from the
				   set 0-i-1. That value is saved in (i-1, j)
				   If we are to use the current item and
				   realise this weight we have to add it to the
				   value of (weight - current item) realised
				   with 0..i-1 items
				 */
				int prev_max = dp[i - 1][j];
				int new_max = items[i].value + dp[i - 1][j - items[i].weight];

				if(new_max > prev_max) {
					/* Adding the new item is better than
					 * the previous min
					 */
					dp[i][j] = new_max;
					used[i][j] = 1;
				} else {
					dp[i][j]= prev_max;
					used[i][j] = 0;
				}
			}
		}
	}
}

int retrace(int weight, int num)
{
	int i = num;
	int x;

	if(weight == 0 || num < 0) {
		printf("\n");
		return 0;
	}

	if (used[i][weight] == 0) {
		return retrace(weight, num - 1);
	} else {
		printf("%8d %8d\n", items[i].value, items[i].weight);
		return items[i].value + retrace(weight - items[i].weight, num - 1);
	}
}

int main(int argc, char **argv)
{
	int weight = 17, num = 4;
	int max_val = 0;

	printf("Enter weight to test: ");
	scanf("%d", &weight);

	initialize(weight, num);
	knapsack(weight, num);
	print_arr(dp, num, weight + 1);
	print_arr(used, num, weight + 1);

	printf("%8s %8s\n", "Value", "Weight");
	max_val = retrace(weight, num - 1);
	printf("max_val: %d\n", max_val);

	return 0;
}

